/**
 * 287. 寻找重复数
 * https://leetcode-cn.com/problems/find-the-duplicate-number/
 */

// /**
//  * @param {number[]} nums
//  * @return {number}
//  */
// function findDuplicate(nums) {
//   const cache = new Array(nums.length).fill(false);
//   for (let i = 0; i < nums.length; i += 1) {
//     if (cache[nums[i]]) {
//       return nums[i];
//     }
//     cache[nums[i]] = true;
//   }
//   return 0;
// }

/**
 * 二分法
 * @param {number[]} nums
 * @return {number}
 */
function findDuplicate(nums) {
  let left = 1;
  let right = nums.length - 1;
  let result = 0;
  let middle = 0;
  let lower = 0;
  while (left <= right) {
    middle = (left + right) >> 1;
    lower = 0;
    for (let i = 0; i < nums.length; i += 1) {
      if (nums[i] <= middle) {
        lower += 1;
      }
    }
    if (lower <= middle) {
      left = middle + 1;
    } else {
      result = middle;
      right = middle - 1;
    }
  }
  return result;
}

console.log(findDuplicate([1, 3, 4, 2, 2]) === 2);
console.log(findDuplicate([3, 1, 3, 4, 2]) === 3);
console.log(findDuplicate([1, 1]) === 1);
console.log(findDuplicate([1, 1, 2]) === 1);
